package com.wangjie.datastructuredesign;

/**
 * @author jieshao
 * @date 2022/5/19 14:05
 * 
 * 根据 Node 类型构建一个双链表
 * 
 * 我们实现的双链表 API 只能从尾部插入元素，也就是说靠近尾部的数据是最近使用的，靠近头部的数据是最久未使用的
 */
public class DoubleList {
    // 头尾虚拟节点
    private Node head, tail;

    // 链表元素数
    private int size;

    public DoubleList() {
        // 初始化双向链表的数据
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // 在链表尾部添加节点 x，时间 o(1)
    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    // 删除链表中的 x 节点(x 一定存在)，由于是双向链表且给的是目标 Node 节点，时间 o(1)
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    // 删除链表中第一个节点，并返回该节点，时间 o(1)
    public Node removeFirst() {
        if (head.next == tail) {
            return null;
        }
        Node first = head.next;
        remove(first);
        return first;
    }

    // 返回链表长度，时间 o(1)
    public int size() {
        return size;
    }
}